#pragma once 
#include <iostream>
#include <utility>
#include <vector>
#include <list>
#include <string>
using namespace std;

// //哈希桶
namespace Bucket
{
	template<class K,class V>
	struct HashNode
	{
		std::pair<K, V> _kv;
		HashNode<K, V>* _next;
        //赋值拷贝
        HashNode(const std::pair<K,V>& kv)
            :_kv(kv)
            ,_next(nullptr)
        {}
    };

	template<class K,class V>
	class HashTable
	{
		typedef HashNode<K, V> Node;
	private:
		//指针数据
		std::vector<Node*> _tables;
		std::size_t _n = 0;//Load factor
	public:
		bool Insert(const std::pair<K, V>& kv)
		{
			if (Find(kv.first)) return false;
			
			//Load factor == 1 扩容
			if (_n ==  _tables.size())
			{
				//扩容
				std::size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
				HashTable<K, V> newHT;
				newHT._tables.resize(newSize,nullptr);

				for (std::size_t i = 0; i < _tables.size(); ++i)
				{
					Node* cur = _tables[i];
					while (cur)
					{
						newHT.Insert(cur->_kv);
						cur = cur->_next;
					}
				}
				newHT._tables.swap(_tables);
			}

			std::size_t hashi = kv.first;
			hashi %= _tables.size();
			
			//头插到对应桶即可
			Node* newnode = new Node(kv);
			newnode->_next = _tables[hashi];
			_tables[hashi] = newnode;

			++_n;
			return true;
		}
		Node* Find(const K& key)
		{
			if (_tables.size() == 0)	return nullptr;
			size_t hashi = key;
			hashi %= _tables.size();
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (cur->_kv.first == key)
				{
					return cur;
				}
				cur = cur->_next;
			}
			return nullptr;
		}
	};

	void TestHT1()
	{
		int a[] = { 20,5,8,9999,10,30,50 };
		HashTable<int, int> ht;
		if (ht.Find(10))
		{
			std::cout << "找到了10" << std::endl;
		}

		for (auto e : a)
		{
			ht.Insert(make_pair(e, e));
		}

        if (ht.Find(10))
		{
			std::cout << "找到了10" << std::endl;
		}
		if (ht.Find(50))
		{
			std::cout << "找到了50" << std::endl;
		}
	}
	
}